package algorithm.arithmetic.围圈报数;

import java.util.ArrayList;
import java.util.List;

/**
 *
 *
 * 有m(m > 0)个人围成一圈，顺序报号(从1开始)。从第一个人开始报数，凡报到n(n > 0)的人退出圈子，然后从第n+1（退出圈子位置的下一个人）个人处重新开始报数（从1开始）， 最后留下来的是原来的第几号?
 *
 * 例如以下为m=15, n=4的情况:
 * 输入:
 * 15 4
 *
 * 输出:
 * 13
 *
 * @author xinchen by 2016/11/25
 * @version 1.0
 */
public class Solution {
    // 有m(m > 0)个人围成一圈，顺序报号(从1开始)。从第一个人开始报数，
    // 凡报到n(n > 0)的人退出圈子，然后从第n+1（退出圈子位置的下一个人）
    // 个人处重新开始报数（从1开始）， 最后留下来的是原来的第几号?
    public static void main(String[] args) {
        int total = Integer.parseInt(args[0]);
        List<Person> persons = new ArrayList<Person>();
        for (int i = 0; i < total; i++) {
            persons.add(new Person(i + 1));
        }

        int index = 0;
        int num = Integer.parseInt(args[1]);
        int count = 0;
        while (!persons.isEmpty() && persons.size() != 1) {
            count++;
            if (count % num == 0) {
                count = 0;
                persons.remove(index);
            } else {
                index++;
            }
            if (persons.size() <= index) {
                index = 0;
            }
        }
        System.out.println(persons.get(0).index);
    }

    private static class Person {
        int index;

        Person(int index) {
            this.index = index;
        }
    }

}
